home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / shells / zsh-3.0-p / zsh-3 / zsh-3.0-pre3 / Src / glob.c < prev    next >
C/C++ Source or Header  |  1996-07-10  |  56KB  |  2,399 lines
  1. /*
  2.  * $Id: glob.c,v 2.28 1996/07/10 20:52:55 hzoli Exp $
  3.  *
  4.  * glob.c - filename generation
  5.  *
  6.  * This file is part of zsh, the Z shell.
  7.  *
  8.  * Copyright (c) 1992-1996 Paul Falstad
  9.  * All rights reserved.
  10.  *
  11.  * Permission is hereby granted, without written agreement and without
  12.  * license or royalty fees, to use, copy, modify, and distribute this
  13.  * software and its documentation for any purpose, provided that the
  14.  * above copyright notice and the following two paragraphs appear in
  15.  * all copies of this software.
  16.  *
  17.  * In no event shall Paul Falstad or the Zsh Development Group be liable
  18.  * to any party for direct, indirect, special, incidental, or consequential
  19.  * damages arising out of the use of this software and its documentation,
  20.  * even if Paul Falstad and the Zsh Development Group have been advised of
  21.  * the possibility of such damage.
  22.  *
  23.  * Paul Falstad and the Zsh Development Group specifically disclaim any
  24.  * warranties, including, but not limited to, the implied warranties of
  25.  * merchantability and fitness for a particular purpose.  The software
  26.  * provided hereunder is on an "as is" basis, and Paul Falstad and the
  27.  * Zsh Development Group have no obligation to provide maintenance,
  28.  * support, updates, enhancements, or modifications.
  29.  *
  30.  */
  31.  
  32. #include "zsh.h"
  33.  
  34. static int
  35. exists(char *s)
  36. {
  37.     char *us = unmeta(s);
  38.  
  39.     return access(us,0) == 0 || readlink(us,NULL,0) == 0;
  40. }
  41.  
  42. static int mode;        /* != 0 if we are parsing glob patterns */
  43. static int pathpos;        /* position in pathbuf                  */
  44. static int matchsz;        /* size of matchbuf                     */
  45. static int matchct;        /* number of matches found              */
  46. static char pathbuf[PATH_MAX];    /* pathname buffer                      */
  47. static char **matchbuf;        /* array of matches                     */
  48. static char **matchptr;        /* &matchbuf[matchct]                   */
  49. static char *colonmod;        /* colon modifiers in qualifier list    */
  50. static ino_t old_ino;        /* ) remember old file and              */
  51. static dev_t old_dev;        /* ) position in path in case           */
  52. static int old_pos;        /* ) matching multiple directories      */
  53.  
  54. typedef struct stat *Statptr;     /* This makes the Ultrix compiler happy.  Go figure. */
  55.  
  56. /* modifier for unit conversions */
  57.  
  58. #define TT_DAYS 0
  59. #define TT_HOURS 1
  60. #define TT_MINS 2
  61. #define TT_WEEKS 3
  62. #define TT_MONTHS 4
  63.  
  64. #define TT_BYTES 0
  65. #define TT_POSIX_BLOCKS 1
  66. #define TT_KILOBYTES 2
  67. #define TT_MEGABYTES 3
  68.  
  69. /* max # of qualifiers */
  70.  
  71. typedef int (*TestMatchFunc) _((struct stat *, long));
  72.  
  73. struct qual {
  74.     struct qual *next;        /* Next qualifier, must match                */
  75.     struct qual *or;        /* Alternative set of qualifiers to match    */
  76.     TestMatchFunc func;        /* Function to call to test match            */
  77.     long data;            /* Argument passed to function               */
  78.     int sense;            /* Whether asserting or negating             */
  79.     int amc;            /* Flag for which time to test (a, m, c)     */
  80.     int range;            /* Whether to test <, > or = (as per signum) */
  81.     int units;            /* Multiplier for time or size, respectively */
  82. };
  83.  
  84. /* Qualifiers pertaining to current pattern */
  85. static struct qual *quals;
  86.  
  87. /* Other state values for current pattern */
  88. static int qualct, qualorct;
  89. static int range, amc, units;
  90. static int gf_nullglob, gf_markdirs, gf_noglobdots, gf_listtypes;
  91.  
  92. /* Prefix, suffix for doing zle trickery */
  93. char *glob_pre, *glob_suf;
  94.  
  95. /* pathname component in filename patterns */
  96.  
  97. struct complist {
  98.     Complist next;
  99.     Comp comp;
  100.     int closure;        /* 1 if this is a (foo/)# */
  101.     int follow;         /* 1 to go thru symlinks */
  102. };
  103. struct comp {
  104.     Comp left, right, next, exclude;
  105.     char *str;
  106.     int stat;
  107. };
  108.  
  109. /* Type of Comp:  a closure with one or two #'s, the end of a *
  110.  * pattern or path component, a piece of path to be added.    */
  111. #define C_ONEHASH    1
  112. #define C_TWOHASH    2
  113. #define C_CLOSURE    (C_ONEHASH|C_TWOHASH)
  114. #define C_LAST        4
  115. #define C_PATHADD    8
  116.  
  117. /* Test macros for the above */
  118. #define CLOSUREP(c)    (c->stat & C_CLOSURE)
  119. #define ONEHASHP(c)    (c->stat & C_ONEHASH)
  120. #define TWOHASHP(c)    (c->stat & C_TWOHASH)
  121. #define LASTP(c)    (c->stat & C_LAST)
  122. #define PATHADDP(c)    (c->stat & C_PATHADD)
  123.  
  124. /* Main entry point to the globbing code for filename globbing. *
  125.  * np points to a node in the list list which will be expanded  *
  126.  * into a series of nodes.                                      */
  127.  
  128. /**/
  129. void
  130. glob(LinkList list, LinkNode np)
  131. {
  132.     struct qual *qo, *qn, *ql;
  133.     LinkNode node = prevnode(np);
  134.     char *str;                /* the pattern                   */
  135.     int sl;                /* length of the pattern         */
  136.     Complist q;                /* pattern after parsing         */
  137.     char *ostr = (char *)getdata(np);    /* the pattern before the parser */
  138.                     /* chops it up                   */
  139.  
  140.     MUSTUSEHEAP("glob");
  141.     if (isset(NOGLOBOPT) || !(str = haswilds(ostr))) {
  142.     untokenize(ostr);
  143.     return;
  144.     }
  145.     if (*str == ':' && str[-1] == Inpar) {
  146.     str[-1] = '\0';
  147.     modify((char **) &getdata(np), &str);
  148.     return;
  149.     }
  150.     str = dupstring(ostr);
  151.     sl = strlen(str);
  152.     uremnode(list, np);
  153.  
  154.     /* Initialise state variables for current file pattern */
  155.     qo = qn = quals = ql = NULL;
  156.     qualct = qualorct = 0;
  157.     colonmod = NULL;
  158.     gf_nullglob = isset(NULLGLOB);
  159.     gf_markdirs = isset(MARKDIRS);
  160.     gf_listtypes = 0;
  161.     gf_noglobdots = unset(GLOBDOTS);
  162.     if (str[sl - 1] == Outpar) {    /* check for qualifiers */
  163.     char *s;
  164.     int sense = 0;            /* bit 0 for match (0)/don't match (1)   */
  165.                     /* bit 1 for follow links (2), don't (0) */
  166.     long data = 0;            /* Any numerical argument required       */
  167.  
  168.     int (*func) _((Statptr, long));
  169.  
  170.     /* Check these are really qualifiers, not a set of *
  171.      * alternatives or exclusions                      */
  172.     for (s = str + sl - 2; s != str; s--)
  173.         if (*s == Bar || *s == Outpar || *s == Inpar
  174.         || (isset(EXTENDEDGLOB) && *s == Tilde))
  175.         break;
  176.     if (*s == Inpar) {
  177.         /* Real qualifiers found. */
  178.         *s++ = '\0';
  179.         while (*s != Outpar && !colonmod) {
  180.         func = (int (*) _((Statptr, long)))0;
  181.         if (idigit(*s)) {
  182.             /* Store numeric argument for qualifier */
  183.             func = qualflags;
  184.             data = 0;
  185.             while (idigit(*s))
  186.             data = data * 010 + (*s++ - '0');
  187.         } else if (*s == ',') {
  188.             /* A comma separates alternative sets of qualifiers */
  189.             s++;
  190.             if (qualct) {
  191.             qn = (struct qual *)hcalloc(sizeof *qn);
  192.             qo->or = qn;
  193.             qo = qn;
  194.             qualorct++;
  195.             qualct = 0;
  196.             ql = NULL;
  197.             }
  198.         } else
  199.             switch (*s++) {
  200.             case ':':
  201.             /* Remaining arguments are history-type     *
  202.              * colon substitutions, handled separately. */
  203.             colonmod = s - 1;
  204.             break;
  205.             case Hat:
  206.             case '^':
  207.             /* Toggle sense:  go from positive to *
  208.              * negative match and vice versa.     */
  209.             sense ^= 1;
  210.             break;
  211.             case '-':
  212.             /* Toggle matching of symbolic links */
  213.             sense ^= 2;
  214.             break;
  215. #ifdef S_IFLNK
  216.             case '@':
  217.             /* Match symbolic links */
  218.             func = qualmode;
  219.             data = S_IFLNK;
  220.             break;
  221. #endif
  222. #ifdef S_IFSOCK
  223.             case Equals:
  224.             case '=':
  225.             /* Match sockets */
  226.             func = qualmode;
  227.             data = S_IFSOCK;
  228.             break;
  229. #endif
  230. #ifdef S_IFIFO
  231.             case 'p':
  232.             /* Match named pipes */
  233.             func = qualmode;
  234.             data = S_IFIFO;
  235.             break;
  236. #endif
  237.             case '/':
  238.             /* Match directories */
  239.             func = qualmode;
  240.             data = S_IFDIR;
  241.             break;
  242.             case '.':
  243.             /* Match regular files */
  244.             func = qualmode;
  245.             data = S_IFREG;
  246.             break;
  247.             case '%':
  248.             /* Match special files: block, *
  249.              * character or any device     */
  250.             if (*s == 'b')
  251.                 s++, func = qualisblk;
  252.             else if (*s == 'c')
  253.                 s++, func = qualischar;
  254.             else
  255.                 func = qualisdev;
  256.             break;
  257.             case Star:
  258.             /* Match executable plain files */
  259.             func = qualiscom;
  260.             break;
  261.             case 'R':
  262.             /* Match world-readable files */
  263.             func = qualflags;
  264.             data = 0004;
  265.             break;
  266.             case 'W':
  267.             /* Match world-writeable files */
  268.             func = qualflags;
  269.             data = 0002;
  270.             break;
  271.             case 'X':
  272.             /* Match world-executable files */
  273.             func = qualflags;
  274.             data = 0001;
  275.             break;
  276.             case 'A':
  277.             func = qualflags;
  278.             data = 0040;
  279.             break;
  280.             case 'I':
  281.             func = qualflags;
  282.             data = 0020;
  283.             break;
  284.             case 'E':
  285.             func = qualflags;
  286.             data = 0010;
  287.             break;
  288.             case 'r':
  289.             /* Match files readable by current process */
  290.             func = qualflags;
  291.             data = 0400;
  292.             break;
  293.             case 'w':
  294.             /* Match files writeable by current process */
  295.             func = qualflags;
  296.             data = 0200;
  297.             break;
  298.             case 'x':
  299.             /* Match files executable by current process */
  300.             func = qualflags;
  301.             data = 0100;
  302.             break;
  303.             case 's':
  304.             /* Match setuid files */
  305.             func = qualflags;
  306.             data = 04000;
  307.             break;
  308.             case 'S':
  309.             /* Match setgid files */
  310.             func = qualflags;
  311.             data = 02000;
  312.             break;
  313.             case 't':
  314.             func = qualflags;
  315.             data = 01000;
  316.             break;
  317.             case 'd':
  318.             /* Match device files by device number  *
  319.              * (as given by stat's st_dev element). */
  320.             func = qualdev;
  321.             data = qgetnum(&s);
  322.             break;
  323.             case 'l':
  324.             /* Match files with the given no. of hard links */
  325.             func = qualnlink;
  326.             amc = -1;
  327.             goto getrange;
  328.             case 'U':
  329.             /* Match files owned by effective user ID */
  330.             func = qualuid;
  331.             data = geteuid();
  332.             break;
  333.             case 'G':
  334.             /* Match files owned by effective group ID */
  335.             func = qualgid;
  336.             data = getegid();
  337.             break;
  338.             case 'u':
  339.             /* Match files owned by given user id */
  340.             func = qualuid;
  341.             /* either the actual uid... */
  342.             if (idigit(*s))
  343.                 data = qgetnum(&s);
  344.             else {
  345.                 /* ... or a user name */
  346.                 struct passwd *pw;
  347.                 char sav, *tt;
  348.  
  349.                 /* Find matching delimiters */
  350.                 tt = get_strarg(s);
  351.                 if (!*tt) {
  352.                 zerr("missing end of name",
  353.                      NULL, 0);
  354.                 data = 0;
  355.                 } else {
  356.                 sav = *tt;
  357.                 *tt = '\0';
  358.  
  359.                 if ((pw = getpwnam(s + 1)))
  360.                     data = pw->pw_uid;
  361.                 else {
  362.                     zerr("unknown user", NULL, 0);
  363.                     data = 0;
  364.                 }
  365.                 if ((*tt = sav) != Outpar)
  366.                     s = tt + 1;
  367.                 else
  368.                     s = tt;
  369.                 }
  370.             }
  371.             break;
  372.             case 'g':
  373.             /* Given gid or group id... works like `u' */
  374.             func = qualgid;
  375.             /* either the actual gid... */
  376.             if (idigit(*s))
  377.                 data = qgetnum(&s);
  378.             else {
  379.                 /* ...or a delimited group name. */
  380.                 struct group *gr;
  381.                 char sav, *tt;
  382.  
  383.                 tt = get_strarg(s);
  384.                 if (!*tt) {
  385.                 zerr("missing end of name",
  386.                      NULL, 0);
  387.                 data = 0;
  388.                 } else {
  389.                 sav = *tt;
  390.                 *tt = '\0';
  391.  
  392.                 if ((gr = getgrnam(s + 1)))
  393.                     data = gr->gr_gid;
  394.                 else {
  395.                     zerr("unknown group", NULL, 0);
  396.                     data = 0;
  397.                 }
  398.                 if ((*tt = sav) != Outpar)
  399.                     s = tt + 1;
  400.                 else
  401.                     s = tt;
  402.                 }
  403.             }
  404.             break;
  405.             case 'o':
  406.             /* Match octal mode of file exactly. *
  407.              * Currently undocumented.           */
  408.             func = qualeqflags;
  409.             data = qgetoctnum(&s);
  410.             break;
  411.             case 'M':
  412.             /* Mark directories with a / */
  413.             gf_markdirs = !(sense & 1);
  414.             break;
  415.             case 'T':
  416.             /* Mark types in a `ls -F' type fashion */
  417.             gf_listtypes = !(sense & 1);
  418.             break;
  419.             case 'N':
  420.             /* Nullglob:  remove unmatched patterns. */
  421.             gf_nullglob = !(sense & 1);
  422.             break;
  423.             case 'D':
  424.             /* Glob dots: match leading dots implicitly */
  425.             gf_noglobdots = sense & 1;
  426.             break;
  427.             case 'a':
  428.             /* Access time in given range */
  429.             amc = 0;
  430.             func = qualtime;
  431.             goto getrange;
  432.             case 'm':
  433.             /* Modification time in given range */
  434.             amc = 1;
  435.             func = qualtime;
  436.             goto getrange;
  437.             case 'c':
  438.             /* Inode creation time in given range */
  439.             amc = 2;
  440.             func = qualtime;
  441.             goto getrange;
  442.             case 'L':
  443.             /* File size (Length) in given range */
  444.             func = qualsize;
  445.             amc = -1;
  446.             /* Get size multiplier */
  447.             units = TT_BYTES;
  448.             if (*s == 'p' || *s == 'P')
  449.                 units = TT_POSIX_BLOCKS, ++s;
  450.             else if (*s == 'k' || *s == 'K')
  451.                 units = TT_KILOBYTES, ++s;
  452.             else if (*s == 'm' || *s == 'M')
  453.                 units = TT_MEGABYTES, ++s;
  454.               getrange:
  455.             /* Get time multiplier */
  456.             if (amc >= 0) {
  457.                 units = TT_DAYS;
  458.                 if (*s == 'h')
  459.                 units = TT_HOURS, ++s;
  460.                 else if (*s == 'm')
  461.                 units = TT_MINS, ++s;
  462.                 else if (*s == 'w')
  463.                 units = TT_WEEKS, ++s;
  464.                 else if (*s == 'M')
  465.                 units = TT_MONTHS, ++s;
  466.             }
  467.             /* See if it's greater than, equal to, or less than */
  468.             if ((range = *s == '+' ? 1 : *s == '-' ? -1 : 0))
  469.                 ++s;
  470.             data = qgetnum(&s);
  471.             break;
  472.  
  473.             default:
  474.             zerr("unknown file attribute", NULL, 0);
  475.             return;
  476.             }
  477.         if (func) {
  478.             /* Requested test is performed by function func */
  479.             if (!qn)
  480.             qn = (struct qual *)hcalloc(sizeof *qn);
  481.             if (ql)
  482.             ql->next = qn;
  483.             ql = qn;
  484.             if (!quals)
  485.             quals = qo = qn;
  486.             qn->func = func;
  487.             qn->sense = sense;
  488.             qn->data = data;
  489.             qn->range = range;
  490.             qn->units = units;
  491.             qn->amc = amc;
  492.             qn = NULL;
  493.             qualct++;
  494.         }
  495.         if (errflag)
  496.             return;
  497.         }
  498.     }
  499.     } else if ((str[sl - 1] == '/') &&
  500.            !((str[sl - 2] == Star) &&
  501.          (str[sl - 3] == Star))) {    /* foo/ == foo(-/) */
  502.     /* No explicit qualifiers, but implicitly match final directory */
  503.     str[sl - 1] = '\0';
  504.     quals = (struct qual *)hcalloc(sizeof *quals);
  505.     quals->func = qualmode;
  506.     quals->data = S_IFDIR;
  507.     quals->sense = 2;
  508.     qualct = 1;
  509.     }
  510.     if (*str == '/') {        /* pattern has absolute path */
  511.     str++;
  512.     pathbuf[0] = '/';
  513.     pathbuf[pathpos = 1] = '\0';
  514.     } else            /* pattern is relative to pwd */
  515.     pathbuf[pathpos = 0] = '\0';
  516.     q = parsepat(str);
  517.     if (!q || errflag) {    /* if parsing failed */
  518.     if (isset(NOBADPATTERN)) {
  519.         untokenize(ostr);
  520.         insertlinknode(list, node, ostr);
  521.         return;
  522.     }
  523.     errflag = 0;
  524.     zerr("bad pattern: %s", ostr, 0);
  525.     return;
  526.     }
  527.  
  528.     /* Initialise receptacle for matched files, *
  529.      * expanded by insert() where necessary.    */
  530.     matchptr = matchbuf = (char **)zalloc((matchsz = 16) * sizeof(char *));
  531.     matchct = 0;
  532.  
  533.     /* Initialise memory of last file matched */
  534.     old_ino = (ino_t) 0;
  535.     old_dev = (dev_t) 0;
  536.     old_pos = -1;
  537.  
  538.     /* The actual processing takes place here: matches go into  *
  539.      * matchbuf.  This is the only top-level call to scanner(). */
  540.     scanner(q);
  541.  
  542.     /* Deal with failures to match depending on options */
  543.     if (matchct)
  544.     badcshglob |= 2;    /* at least one cmd. line expansion O.K. */
  545.     else if (!gf_nullglob)
  546.     if (isset(CSHNULLGLOB)) {
  547.         badcshglob |= 1;    /* at least one cmd. line expansion failed */
  548.     } else if (unset(NONOMATCH)) {
  549.         zerr("no matches found: %s", ostr, 0);
  550.         free(matchbuf);
  551.         return;
  552.     } else {
  553.         /* treat as an ordinary string */
  554.         untokenize(*matchptr++ = dupstring(ostr));
  555.         matchct = 1;
  556.     }
  557.     /* Sort arguments in to lexical (and possibly numeric) order. *
  558.      * This is reversed to facilitate insertion into the list.    */
  559.     qsort((void *) & matchbuf[0], matchct, sizeof(char *),
  560.            (int (*) _((const void *, const void *)))notstrcmp);
  561.  
  562.     matchptr = matchbuf;
  563.     while (matchct--)        /* insert matches in the arg list */
  564.     insertlinknode(list, node, *matchptr++);
  565.     free(matchbuf);
  566. }
  567.  
  568. /* get number after qualifier */
  569.  
  570. /**/
  571. long
  572. qgetnum(char **s)
  573. {
  574.     long v = 0;
  575.  
  576.     if (!idigit(**s)) {
  577.     zerr("number expected", NULL, 0);
  578.     return 0;
  579.     }
  580.     while (idigit(**s))
  581.     v = v * 10 + *(*s)++ - '0';
  582.     return v;
  583. }
  584.  
  585. /* get octal number after qualifier */
  586.  
  587. /**/
  588. long
  589. qgetoctnum(char **s)
  590. {
  591.     long v = 0;
  592.  
  593.     if (!idigit(**s)) {
  594.     zerr("octal number expected", NULL, 0);
  595.     return 0;
  596.     }
  597.     while (**s >= '0' && **s <= '7')
  598.     v = v * 010 + *(*s)++ - '0';
  599.     return v;
  600. }
  601.  
  602. /* Return the order of two strings, taking into account *
  603.  * possible numeric order if NUMERICGLOBSORT is set.    *
  604.  * The comparison here is reversed.                     */
  605.  
  606. /**/
  607. int
  608. notstrcmp(char **a, char **b)
  609. {
  610.     char *c = *b, *d = *a;
  611.     int cmp;
  612.  
  613. #ifdef HAVE_STRCOLL
  614.     cmp = strcoll(c, d);
  615. #endif
  616.     for (; *c == *d && *c; c++, d++);
  617. #ifndef HAVE_STRCOLL
  618.     cmp = (int)STOUC(*c) - (int)STOUC(*d);
  619. #endif
  620.     if (isset(NUMERICGLOBSORT) && (idigit(*c) || idigit(*d))) {
  621.     for (; c > *b && idigit(c[-1]); c--, d--);
  622.     if (idigit(*c) && idigit(*d)) {
  623.         while (*c == '0')
  624.         c++;
  625.         while (*d == '0')
  626.         d++;
  627.         for (; idigit(*c) && *c == *d; c++, d++);
  628.         if (idigit(*c) || idigit(*d)) {
  629.         cmp = (int)STOUC(*c) - (int)STOUC(*d);
  630.         while (idigit(*c) && idigit(*d))
  631.             c++, d++;
  632.         if (idigit(*c) && !idigit(*d))
  633.             return 1;
  634.         if (idigit(*d) && !idigit(*c))
  635.             return -1;
  636.         }
  637.     }
  638.     }
  639.     return cmp;
  640. }
  641.  
  642. /* add a match to the list */
  643.  
  644. /**/
  645. void
  646. insert(char *s)
  647. {
  648.     struct stat buf, buf2, *bp;
  649.     int statted = 0;
  650.  
  651.     if (gf_listtypes || gf_markdirs) {
  652.     /* Add the type marker to the end of the filename */
  653.     statted = 1;
  654.     if (!lstat(unmeta(s), &buf) && (gf_listtypes || S_ISDIR(buf.st_mode))) {
  655.         char *t;
  656.         int ll = strlen(s);
  657.  
  658.         t = (char *)ncalloc(ll + 2);
  659.         strcpy(t, s);
  660.         t[ll] = file_type(buf.st_mode);
  661.         t[ll + 1] = '\0';
  662.         s = t;
  663.     }
  664.     }
  665.     if (qualct || qualorct) {
  666.     /* Go through the qualifiers, rejecting the file if appropriate */
  667.     struct qual *qo, *qn;
  668.     int t = 0;        /* reject file unless t is set */
  669.  
  670.     if (statted || lstat(unmeta(s), &buf) >= 0) {
  671.         statted = 0;
  672.         for (qo = quals; qo && !t; qo = qo->or) {
  673.  
  674.         t = 1;
  675.         for (qn = qo; t && qn && qn->func; qn = qn->next) {
  676.             range = qn->range;
  677.             amc = qn->amc;
  678.             units = qn->units;
  679.             if ((qn->sense & 2) && !statted) {
  680.             /* If (sense & 2), we're following links */
  681.             statted = 1;
  682.             stat(unmeta(s), &buf2);
  683.             }
  684.             bp = (qn->sense & 2) ? &buf2 : &buf;
  685.             /* Reject the file if the function returned zero *
  686.              * and the sense was positive (sense == 0), or   *
  687.              * vice versa.                                   */
  688.             if (!(!!((qn->func) (bp, qn->data)) ^
  689.               (qn->sense & 1))) {
  690.             t = 0;
  691.             break;
  692.             }
  693.         }
  694.         }
  695.     }
  696.     if (!t)
  697.         return;
  698.     }
  699.     if (colonmod) {
  700.     /* Handle the remainder of the qualifer:  e.g. (:r:s/foo/bar/). */
  701.     char *cm2 = colonmod;
  702.  
  703.     modify(&s, &cm2);
  704.     }
  705.     *matchptr++ = s;
  706.     if (++matchct == matchsz) {
  707.     matchbuf = (char **)realloc((char *)matchbuf,
  708.                     sizeof(char **) * (matchsz *= 2));
  709.  
  710.     matchptr = matchbuf + matchct;
  711.     }
  712. }
  713.  
  714. /* Return the trailing character for marking file types */
  715.  
  716. /**/
  717. char
  718. file_type(mode_t filemode)
  719. {
  720.     switch (filemode & S_IFMT) {/* screw POSIX */
  721.     case S_IFDIR:
  722.     return '/';
  723. #ifdef S_IFIFO
  724.     case S_IFIFO:
  725.     return '|';
  726. #endif
  727.     case S_IFCHR:
  728.     return '%';
  729.     case S_IFBLK:
  730.     return '#';
  731. #ifdef S_IFLNK
  732.     case S_IFLNK:
  733.     return /* (access(pbuf, F_OK) == -1) ? '&' :*/ '@';
  734. #endif
  735. #ifdef S_IFSOCK
  736.     case S_IFSOCK:
  737.     return '=';
  738. #endif
  739.     default:
  740.     if (filemode & 0111)
  741.         return '*';
  742.     else
  743.         return ' ';
  744.     }
  745. }
  746.  
  747. /* check to see if str is eligible for filename generation
  748.  * It returns NULL if no wilds or modifiers found.
  749.  * If a leading % is immediately followed by a ?, that single
  750.  * ? is not treated as a wildcard.
  751.  * If str has wilds it returns a pointer to the first wildcard.
  752.  * If str has no wilds but ends in a (:...) type modifier it returns
  753.  * a pointer to the colon.
  754.  * If str has no wilds but ends in (...:...) it returns a pointer
  755.  * to the terminating null character of str.
  756.  */
  757.  
  758. /**/
  759. char *
  760. haswilds(char *str)
  761. {
  762.     char *mod = NULL;
  763.     int parlev = 0;
  764.  
  765.     if ((*str == Inbrack || *str == Outbrack) && !str[1])
  766.     return NULL;
  767.  
  768.     /* If % is immediately followed by ?, then that ? is     *
  769.      * not treated as a wildcard.  This is so you don't have *
  770.      * to escape job references such as %?foo.               */
  771.     if (str[0] == '%' && str[1] == Quest)
  772.     str[1] = '?';
  773.     for (; *str; str++)
  774.     switch (*str) {
  775.     case Inpar:
  776.         parlev++;
  777.         break;
  778.     case Outpar:
  779.         if (! --parlev && str[1])
  780.         mod = NULL;
  781.         break;
  782.     case ':':
  783.         if (parlev == 1)
  784.         mod = str;
  785.         break;
  786.     case Bar:
  787.         if (!parlev) {
  788.         *str = '|';
  789.         break;
  790.         } /* else fall through */
  791.     case Pound:
  792.     case Hat:
  793.     case Star:
  794.     case Inbrack:
  795.     case Inang:
  796.     case Quest:
  797.         return str;
  798.     }
  799.     if (!mod || parlev)
  800.     return NULL;
  801.     if (mod[-1] == Inpar)
  802.     return mod;
  803.     return str;
  804. }
  805.  
  806. /* check to see if str is eligible for brace expansion */
  807.  
  808. /**/
  809. int
  810. hasbraces(char *str)
  811. {
  812.     int mb, bc, cmct1, cmct2;
  813.     char *lbr = NULL;
  814.  
  815.     if (isset(BRACECCL)) {
  816.     /* In this case, any properly formed brace expression  *
  817.      * will match and expand to the characters in between. */
  818.     for (mb = bc = 0; *str; ++str)
  819.         if (*str == Inbrace) {
  820.         if (!mb && str[1] == Outbrace)
  821.             *str++ = '{', *str = '}';
  822.         else if (++bc > mb)
  823.             mb = bc;
  824.         } else if (*str == Outbrace)
  825.         if (--bc < 0)
  826.             return (0);
  827.     return (mb && bc == 0);
  828.     }
  829.     /* Otherwise we need to look for... */
  830.     for (mb = bc = cmct1 = cmct2 = 0; *str; str++) {
  831.     if (*str == Inbrace) {
  832.         if (!bc)
  833.         lbr = str;
  834.         bc++;
  835.         if (str[2] == '-' && str[3] && str[4] == Outbrace) { /* {a-z} */
  836.         /* ...character ranges... */
  837.         cmct1++;
  838.         if (bc == 1)
  839.             cmct2++;
  840.         }
  841.     } else if (*str == Outbrace) {
  842.         /* (see if we've finished this set of braces) */
  843.         bc--;
  844.         if (!bc) {
  845.         if (!cmct2) {
  846.             *lbr = '{';
  847.             *str = '}';
  848.         }
  849.         cmct2 = 0;
  850.         }
  851.     } else if ((*str == Comma || (*str == '.' && str[1] == '.')) && bc) {
  852.         /* ...or comma'd ranges or numeric ranges. */
  853.         cmct1++;
  854.         if (bc == 1)
  855.         cmct2++;
  856.     }
  857.     if (bc > mb)
  858.         mb = bc;
  859.     if (bc < 0)
  860.         return 0;
  861.     }
  862.     return (mb && bc == 0 && cmct1);
  863. }
  864.  
  865. /* expand stuff like >>*.c */
  866.  
  867. /**/
  868. int
  869. xpandredir(struct redir *fn, LinkList tab)
  870. {
  871.     LinkList fake;
  872.     char *nam;
  873.     struct redir *ff;
  874.     int ret = 0;
  875.  
  876.     /* Stick the name in a list... */
  877.     fake = newlinklist();
  878.     addlinknode(fake, fn->name);
  879.     /* ...which undergoes all the usual shell expansions */
  880.     prefork(fake, unset(NOMULTIOS) ? 0 : 4);
  881.     /* Globbing is only done for multios. */
  882.     if (!errflag && unset(NOMULTIOS))
  883.     globlist(fake);
  884.     if (errflag)
  885.     return 0;
  886.     if (nonempty(fake) && !nextnode(firstnode(fake))) {
  887.     /* Just one match, the usual case. */
  888.     char *s = peekfirst(fake);
  889.     fn->name = s;
  890.     untokenize(s);
  891.     if (fn->type == MERGEIN || fn->type == MERGEOUT) {
  892.         if (s[0] == '-' && !s[1])
  893.         fn->type = CLOSE;
  894.         else if (s[0] == 'p' && !s[1]) 
  895.         fn->fd2 = (fn->type == MERGEOUT) ? coprocout : coprocin;
  896.         else {
  897.         while (idigit(*s))
  898.             s++;
  899.         if (!*s && s > fn->name)
  900.             fn->fd2 = zstrtol(fn->name, NULL, 10);
  901.         else if (fn->type == MERGEIN)
  902.             zerr("file number expected", NULL, 0);
  903.         else
  904.             fn->type = ERRWRITE;
  905.         }
  906.     }
  907.     } else if (fn->type == MERGEIN)
  908.     zerr("file number expected", NULL, 0);
  909.     else {
  910.     if (fn->type == MERGEOUT)
  911.         fn->type = ERRWRITE;
  912.     while ((nam = (char *)ugetnode(fake))) {
  913.         /* Loop over matches, duplicating the *
  914.          * redirection for each file found.   */
  915.         ff = (struct redir *)alloc(sizeof *ff);
  916.         *ff = *fn;
  917.         ff->name = nam;
  918.         addlinknode(tab, ff);
  919.         ret = 1;
  920.     }
  921.     }
  922.     return ret;
  923. }
  924.  
  925. /* concatenate s1 and s2 in dynamically allocated buffer */
  926.  
  927. /**/
  928. char *
  929. dyncat(char *s1, char *s2)
  930. {
  931.     /* This version always uses space from the current heap. */
  932.     char *ptr;
  933.  
  934.     ptr = (char *)ncalloc(strlen(s1) + strlen(s2) + 1);
  935.     strcpy(ptr, s1);
  936.     strcat(ptr, s2);
  937.     return ptr;
  938. }
  939.  
  940. /* concatenate s1, s2, and s3 in dynamically allocated buffer */
  941.  
  942. /**/
  943. char *
  944. tricat(char *s1, char *s2, char *s3)
  945. {
  946.     /* This version always uses permanently-allocated space. */
  947.     char *ptr;
  948.  
  949.     ptr = (char *)zalloc(strlen(s1) + strlen(s2) + strlen(s3) + 1);
  950.     strcpy(ptr, s1);
  951.     strcat(ptr, s2);
  952.     strcat(ptr, s3);
  953.     return ptr;
  954. }
  955.  
  956. /* brace expansion */
  957.  
  958. /**/
  959. void
  960. xpandbraces(LinkList list, LinkNode *np)
  961. {
  962.     LinkNode node = (*np), last = prevnode(node);
  963.     char *str = (char *)getdata(node), *str3 = str, *str2;
  964.     int prev, bc, comma, dotdot;
  965.  
  966.     for (; *str != Inbrace; str++);
  967.     /* First, match up braces and see what we have. */
  968.     for (str2 = str, bc = comma = dotdot = 0; *str2; ++str2)
  969.     if (*str2 == Inbrace)
  970.         ++bc;
  971.     else if (*str2 == Outbrace) {
  972.         if (--bc == 0)
  973.         break;
  974.     } else if (bc == 1)
  975.         if (*str2 == Comma)
  976.         ++comma;    /* we have {foo,bar} */
  977.         else if (*str2 == '.' && str2[1] == '.')
  978.         dotdot++;    /* we have {num1..num2} */
  979.     if (!comma && !bc && dotdot) {
  980.     /* Expand range like 0..10 numerically: comma or recursive
  981.        brace expansion take precedence. */
  982.     char *dots, *p;
  983.     LinkNode olast = last;
  984.     /* Get the first number of the range */
  985.     int rstart = zstrtol(str+1,&dots,10), rend = 0, err = 0, rev = 0;
  986.     int wid1 = (dots - str) - 1, wid2 = (str2 - dots) - 2;
  987.     int strp = str - str3;
  988.       
  989.     if (dots == str + 1 || *dots != '.' || dots[1] != '.')
  990.         err++;
  991.     else {
  992.         /* Get the last number of the range */
  993.         rend = zstrtol(dots+2,&p,10);
  994.         if (p == dots+2 || p != str2)
  995.         err++;
  996.     }
  997.     if (!err) {
  998.         /* If either no. begins with a zero, pad the output with   *
  999.          * zeroes. Otherwise, choose a min width to suppress them. */
  1000.         int minw = (str[1] == '0') ? wid1 : (dots[2] == '0' ) ? wid2 :
  1001.         (wid2 > wid1) ? wid1 : wid2;
  1002.         if (rstart > rend) {
  1003.         /* Handle decreasing ranges correctly. */
  1004.         int rt = rend;
  1005.         rend = rstart;
  1006.         rstart = rt;
  1007.         rev = 1;
  1008.         }
  1009.         uremnode(list, node);
  1010.         for (; rend >= rstart; rend--) {
  1011.         /* Node added in at end, so do highest first */
  1012.         p = dupstring(str3);
  1013.         sprintf(p + strp, "%0*d", minw, rend);
  1014.         strcat(p + strp, str2 + 1);
  1015.         insertlinknode(list, last, p);
  1016.         if (rev)    /* decreasing:  add in reverse order. */
  1017.             last = nextnode(last);
  1018.         }
  1019.         *np = nextnode(olast);
  1020.         return;
  1021.     }
  1022.     }
  1023.     if (!comma && !bc && isset(BRACECCL)) {    /* {a-mnop} */
  1024.     /* Here we expand each character to a separate node,      *
  1025.      * but also ranges of characters like a-m.  ccl is a      *
  1026.      * set of flags saying whether each character is present; *
  1027.      * the final list is in lexical order.                    */
  1028.     char ccl[256], *p;
  1029.     unsigned char c1, c2, lastch;
  1030.  
  1031.     uremnode(list, node);
  1032.     memset(ccl, 0, sizeof(ccl) / sizeof(ccl[0]));
  1033.     for (p = str + 1, lastch = 0; p < str2;) {
  1034.         if (itok(c1 = *p++))
  1035.         c1 = ztokens[c1 - STOUC(Pound)];
  1036.         if (itok(c2 = *p))
  1037.         c2 = ztokens[c2 - STOUC(Pound)];
  1038.         if (c1 == '-' && lastch && p < str2 && (int)lastch <= (int)c2) {
  1039.         while ((int)lastch < (int)c2)
  1040.             ccl[lastch++] = 1;
  1041.         lastch = 0;
  1042.         } else
  1043.         ccl[lastch = c1] = 1;
  1044.     }
  1045.     strcpy(str + 1, str2 + 1);
  1046.     for (p = ccl + 255; p-- > ccl;)
  1047.         if (*p) {
  1048.         *str = p - ccl;
  1049.         insertlinknode(list, last, dupstring(str3));
  1050.         }
  1051.     *np = nextnode(last);
  1052.     return;
  1053.     }
  1054.     if (str[2] == '-' && str[3] && str[4] == Outbrace) { /* {a-z} */
  1055.     /* Now any other ranges present: note this only happens       *
  1056.          * for a pattern like {<char>-<char>}, but it happens for ANY *
  1057.          * character <char>, so {,-z} does this (possibly a bug).     */
  1058.     char c1, c2;
  1059.  
  1060.     uremnode(list, node);
  1061.     chuck(str);
  1062.     c1 = *str;
  1063.     chuck(str);
  1064.     chuck(str);
  1065.     c2 = *str;
  1066.     chuck(str);
  1067.     if (itok(c1))
  1068.         c1 = ztokens[c1 - Pound];
  1069.     if (itok(c2))
  1070.         c2 = ztokens[c2 - Pound];
  1071.     if (c1 < c2)
  1072.         for (; c2 >= c1; c2--) {    /* {a-z} */
  1073.         *str = c2;
  1074.         insertlinknode(list, last, dupstring(str3));
  1075.     } else
  1076.         for (; c2 <= c1; c2++) {    /* {z-a} */
  1077.         *str = c2;
  1078.         insertlinknode(list, last, dupstring(str3));
  1079.         }
  1080.     *np = nextnode(last);
  1081.     return;
  1082.     }
  1083.     prev = str - str3;
  1084.     str2 = getparen(str++);
  1085.     if (!str2) {
  1086.     zerr("how did you get this error?", NULL, 0);
  1087.     return;
  1088.     }
  1089.     uremnode(list, node);
  1090.     node = last;
  1091.     /* Finally, normal comma expansion               *
  1092.      * str1{foo,bar}str2 -> str1foostr2 str1barstr2. *
  1093.      * Any number of intervening commas is allowed.  */
  1094.     for (;;) {
  1095.     char *zz, *str4;
  1096.     int cnt;
  1097.  
  1098.     for (str4 = str, cnt = 0; cnt || (*str != Comma && *str !=
  1099.                       Outbrace); str++)
  1100.         if (*str == Inbrace)
  1101.         cnt++;
  1102.         else if (*str == Outbrace)
  1103.         cnt--;
  1104.         else if (!*str)
  1105.         exit(10);    /* slightly overemphatic, perhaps??? */
  1106.     /* Concatenate the string before the braces (str3), the section *
  1107.      * just found (str4) and the text after the braces (str2)       */
  1108.     zz = (char *)ncalloc(prev + (str - str4) + strlen(str2) + 1);
  1109.     ztrncpy(zz, str3, prev);
  1110.     strncat(zz, str4, str - str4);
  1111.     strcat(zz, str2);
  1112.     /* and add this text to the argument list. */
  1113.     insertlinknode(list, node, zz);
  1114.     incnode(node);
  1115.     if (*str != Outbrace)
  1116.         str++;
  1117.     else
  1118.         break;
  1119.     }
  1120.     *np = nextnode(last);
  1121. }
  1122.  
  1123. /* get closing paren, given pointer to opening paren */
  1124.  
  1125. /**/
  1126. char *
  1127. getparen(char *str)
  1128. {
  1129.     int cnt = 1;
  1130.     char typein = *str++, typeout = typein + 1;
  1131.  
  1132.     for (; *str && cnt; str++)
  1133.     if (*str == typein)
  1134.         cnt++;
  1135.     else if (*str == typeout)
  1136.         cnt--;
  1137.     if (!str && cnt)
  1138.     return NULL;
  1139.     return str;
  1140. }
  1141.  
  1142. /* check to see if a matches b (b is not a filename pattern) */
  1143.  
  1144. /**/
  1145. int
  1146. matchpat(char *a, char *b)
  1147. {
  1148.     Comp c;
  1149.     int val, len;
  1150.     char *b2;
  1151.  
  1152.     len = strlen(b);
  1153.     b2 = (char *)alloc(len + 3);
  1154.     strcpy(b2 + 1, b);
  1155.     b2[0] = Inpar;
  1156.     b2[len + 1] = Outpar;
  1157.     b2[len + 2] = '\0';
  1158.     c = parsereg(b2);
  1159.     if (!c) {
  1160.     zerr("bad pattern: %s", b, 0);
  1161.     return 0;
  1162.     }
  1163.     val = domatch(a, c, 0);
  1164.     return val;
  1165. }
  1166.  
  1167. /* do the ${foo%%bar}, ${foo#bar} stuff */
  1168. /* please do not laugh at this code. */
  1169.  
  1170. /* Having found a match in getmatch, decide what part of string
  1171.  * to return.  The matched part starts b characters into string s
  1172.  * and finishes e characters in: 0 <= b <= e <= strlen(s)
  1173.  * (yes, empty matches should work).
  1174.  * Bits 3 and higher in fl are used: the flags are
  1175.  *   8:        Result is matched portion.
  1176.  *  16:        Result is unmatched portion.
  1177.  *        (N.B. this should be set for standard ${foo#bar} etc. matches.)
  1178.  *  32:        Result is numeric position of start of matched portion.
  1179.  *  64:        Result is numeric position of end of matched portion.
  1180.  * 128:        Result is length of matched portion.
  1181.  */
  1182.  
  1183. /**/
  1184. char *
  1185. get_match_ret(char *s, int b, int e, int fl)
  1186. {
  1187.     char buf[80], *r, *p, *rr;
  1188.     int ll = 0, l = strlen(s), bl = 0, t = 0, i;
  1189.  
  1190.     if (fl & 8)            /* matched portion */
  1191.     ll += 1 + (e - b);
  1192.     if (fl & 16)        /* unmatched portion */
  1193.     ll += 1 + (l - (e - b));
  1194.     if (fl & 32) {
  1195.     /* position of start of matched portion */
  1196.     sprintf(buf, "%d ", b + 1);
  1197.     ll += (bl = strlen(buf));
  1198.     }
  1199.     if (fl & 64) {
  1200.     /* position of end of matched portion */
  1201.     sprintf(buf + bl, "%d ", e + 1);
  1202.     ll += (bl = strlen(buf));
  1203.     }
  1204.     if (fl & 128) {
  1205.     /* length of matched portion */
  1206.     sprintf(buf + bl, "%d ", e - b);
  1207.     ll += (bl = strlen(buf));
  1208.     }
  1209.     if (bl)
  1210.     buf[bl - 1] = '\0';
  1211.  
  1212.     rr = r = (char *)ncalloc(ll);
  1213.  
  1214.     if (fl & 8) {
  1215.     /* copy matched portion to new buffer */
  1216.     for (i = b, p = s + b; i < e; i++)
  1217.         *rr++ = *p++;
  1218.     t = 1;
  1219.     }
  1220.     if (fl & 16) {
  1221.     /* Copy unmatched portion to buffer.  If both portions *
  1222.      * requested, put a space in between (why?)            */
  1223.     if (t)
  1224.         *rr++ = ' ';
  1225.     /* there may be unmatched bits at both beginning and end of string */
  1226.     for (i = 0, p = s; i < b; i++)
  1227.         *rr++ = *p++;
  1228.     for (i = e, p = s + e; i < l; i++)
  1229.         *rr++ = *p++;
  1230.     t = 1;
  1231.     }
  1232.     *rr = '\0';
  1233.     if (bl) {
  1234.     /* if there was a buffer (with a numeric result), add it; *
  1235.      * if there was other stuff too, stick in a space first.  */
  1236.     if (t)
  1237.         *rr++ = ' ';
  1238.     strcpy(rr, buf);
  1239.     }
  1240.     return r;
  1241. }
  1242.  
  1243. /* It is called from paramsubst to get the match for ${foo#bar} etc.
  1244.  * Bits of fl determines the required action:
  1245.  *   bit 0: match the end instead of the beginning (% or %%)
  1246.  *   bit 1: % or # was doubled so get the longest match
  1247.  *   bit 2: substring match
  1248.  *   bit 3: include the matched portion
  1249.  *   bit 4: include the unmatched portion
  1250.  *   bit 5: the index of the beginning
  1251.  *   bit 6: the index of the end
  1252.  *   bit 7: the length of the match
  1253.  *   bit 8: match the complete string
  1254.  * *sp points to the string we have to modify. The n'th match will be
  1255.  * returned in *sp. ncalloc is used to get memory for the result string.
  1256.  */
  1257.  
  1258. /**/
  1259. int
  1260. getmatch(char **sp, char *pat, int fl, int n)
  1261. {
  1262.     Comp c;
  1263.     char *s = *sp, *t, sav;
  1264.     int i, j, l = strlen(*sp);
  1265.  
  1266.     c = parsereg(pat);
  1267.     if (!c) {
  1268.     zerr("bad pattern: %s", pat, 0);
  1269.     return 1;
  1270.     }
  1271.     if (fl & 256) {
  1272.     i = domatch(s, c, 0);
  1273.     *sp = get_match_ret(*sp, 0, domatch(s, c, 0) ? l : 0, fl);
  1274.     if (! **sp && (((fl & 8) && !i) || ((fl & 16) && i)))
  1275.         return 0;
  1276.     return 1;
  1277.     }
  1278.     switch (fl & 7) {
  1279.     case 0:
  1280.     /* Smallest possible match at head of string:    *
  1281.      * start adding characters until we get a match. */
  1282.     for (i = 0, t = s; i <= l; i++, t++) {
  1283.         sav = *t;
  1284.         *t = '\0';
  1285.         if (domatch(s, c, 0) && !--n) {
  1286.         *t = sav;
  1287.         *sp = get_match_ret(*sp, 0, i, fl);
  1288.         return 1;
  1289.         }
  1290.         if ((*t = sav) == Meta)
  1291.         i++, t++;
  1292.     }
  1293.     break;
  1294.  
  1295.     case 1:
  1296.     /* Smallest possible match at tail of string:  *
  1297.      * move back down string until we get a match. */
  1298.     for (t = s + l; t >= s; t--) {
  1299.         if (domatch(t, c, 0) && !--n) {
  1300.         *sp = get_match_ret(*sp, t - s, l, fl);
  1301.         return 1;
  1302.         }
  1303.         if (t > s+1 && t[-2] == Meta)
  1304.         t--;
  1305.     }
  1306.     break;
  1307.  
  1308.     case 2:
  1309.     /* Largest possible match at head of string:        *
  1310.      * delete characters from end until we get a match. */
  1311.     for (t = s + l; t > s; t--) {
  1312.         sav = *t;
  1313.         *t = '\0';
  1314.         if (domatch(s, c, 0) && !--n) {
  1315.         *t = sav;
  1316.         *sp = get_match_ret(*sp, 0, t - s, fl);
  1317.         return 1;
  1318.         }
  1319.         *t = sav;
  1320.         if (t >= s+2 && t[-2] == Meta)
  1321.         t--;
  1322.     }
  1323.     break;
  1324.  
  1325.     case 3:
  1326.     /* Largest possible match at tail of string:       *
  1327.      * move forward along string until we get a match. */
  1328.     for (i = 0, t = s; i < l; i++, t++) {
  1329.         if (domatch(t, c, 0) && !--n) {
  1330.         *sp = get_match_ret(*sp, i, l, fl);
  1331.         return 1;
  1332.         }
  1333.         if (*t == Meta)
  1334.         i++, t++;
  1335.     }
  1336.     break;
  1337.  
  1338.     case 4:
  1339.     /* Smallest at start, but matching substrings. */
  1340.     if (domatch(s + l, c, 0) && !--n) {
  1341.         *sp = get_match_ret(*sp, 0, 0, fl);
  1342.         return 1;
  1343.     }
  1344.     for (i = 1; i <= l; i++) {
  1345.         for (t = s, j = i; j <= l; j++, t++) {
  1346.         sav = s[j];
  1347.         s[j] = '\0';
  1348.         if (domatch(t, c, 0) && !--n) {
  1349.             s[j] = sav;
  1350.             *sp = get_match_ret(*sp, t - s, j, fl);
  1351.             return 1;
  1352.         }
  1353.         if ((s[j] = sav) == Meta)
  1354.             j++;
  1355.         if (*t == Meta)
  1356.             t++;
  1357.         }
  1358.         if (s[i] == Meta)
  1359.         i++;
  1360.     }
  1361.     break;
  1362.  
  1363.     case 5:
  1364.     /* Smallest at end, matching substrings */
  1365.     if (domatch(s + l, c, 0) && !--n) {
  1366.         *sp = get_match_ret(*sp, l, l, fl);
  1367.         return 1;
  1368.     }
  1369.     for (i = l; i--;) {
  1370.         if (i && s[i-1] == Meta)
  1371.         i--;
  1372.         for (t = s + l, j = i; j >= 0; j--, t--) {
  1373.         sav = *t;
  1374.         *t = '\0';
  1375.         if (domatch(s + j, c, 0) && !--n) {
  1376.             *t = sav;
  1377.             *sp = get_match_ret(*sp, j, t - s, fl);
  1378.             return 1;
  1379.         }
  1380.         *t = sav;
  1381.         if (t >= s+2 && t[-2] == Meta)
  1382.             t--;
  1383.         if (j >= 2 && s[j-2] == Meta)
  1384.             j--;
  1385.         }
  1386.     }
  1387.     break;
  1388.  
  1389.     case 6:
  1390.     /* Largest at start, matching substrings. */
  1391.     for (i = l; i; i--) {
  1392.         for (t = s, j = i; j <= l; j++, t++) {
  1393.         sav = s[j];
  1394.         s[j] = '\0';
  1395.         if (domatch(t, c, 0) && !--n) {
  1396.             s[j] = sav;
  1397.             *sp = get_match_ret(*sp, t - s, j, fl);
  1398.             return 1;
  1399.         }
  1400.         if ((s[j] = sav) == Meta)
  1401.             j++;
  1402.         if (*t == Meta)
  1403.             t++;
  1404.         }
  1405.         if (i >= 2 && s[i-2] == Meta)
  1406.         i--;
  1407.     }
  1408.     if (domatch(s + l, c, 0) && !--n) {
  1409.         *sp = get_match_ret(*sp, 0, 0, fl);
  1410.         return 1;
  1411.     }
  1412.     break;
  1413.  
  1414.     case 7:
  1415.     /* Largest at end, matching substrings. */
  1416.     for (i = 0; i < l; i++) {
  1417.         for (t = s + l, j = i; j >= 0; j--, t--) {
  1418.         sav = *t;
  1419.         *t = '\0';
  1420.         if (domatch(s + j, c, 0) && !--n) {
  1421.             *t = sav;
  1422.             *sp = get_match_ret(*sp, j, t - s, fl);
  1423.             return 1;
  1424.         }
  1425.         *t = sav;
  1426.         if (t >= s+2 && t[-2] == Meta)
  1427.             t--;
  1428.         if (j >= 2 && s[j-2] == Meta)
  1429.             j--;
  1430.         }
  1431.         if (s[i] == Meta)
  1432.         i++;
  1433.     }
  1434.     if (domatch(s + l, c, 0) && !--n) {
  1435.         *sp = get_match_ret(*sp, l, l, fl);
  1436.         return 1;
  1437.     }
  1438.     break;
  1439.     }
  1440.     /* munge the whole string */
  1441.     *sp = get_match_ret(*sp, 0, 0, fl);
  1442.     return 1;
  1443. }
  1444.  
  1445. /* Add a component to pathbuf: This keeps track of how    *
  1446.  * far we are into a file name, since each path component *
  1447.  * must be matched separately.                            */
  1448.  
  1449. static int addpath _((char *s));
  1450.  
  1451. static int
  1452. addpath(char *s)
  1453. {
  1454.     if ((int)strlen(s) + pathpos >= PATH_MAX)
  1455.     return 0;
  1456.     while ((pathbuf[pathpos++] = *s++));
  1457.     pathbuf[pathpos - 1] = '/';
  1458.     pathbuf[pathpos] = '\0';
  1459.     return 1;
  1460. }
  1461.  
  1462. /* return full path for s, which has path as *
  1463.  * already added to pathbuf                  */
  1464.  
  1465. /**/
  1466. char *
  1467. getfullpath(char *s)
  1468. {
  1469.     static char buf[PATH_MAX];
  1470.  
  1471.     strcpy(buf, pathbuf);
  1472.     strcat(buf, s);
  1473.     return buf;
  1474. }
  1475.  
  1476. /* Do the globbing:  scanner is called recursively *
  1477.  * with successive bits of the path until we've    *
  1478.  * tried all of it.                                */
  1479.  
  1480. /**/
  1481. void
  1482. scanner(Complist q)
  1483. {
  1484.     Comp c;
  1485.     int closure;
  1486.     struct stat st;
  1487.  
  1488.     if (!q)
  1489.     return;
  1490.  
  1491.     /* make sure we haven't just done this one. */
  1492.     if (q->closure && old_pos != pathpos &&
  1493.     stat((*pathbuf) ? unmeta(pathbuf) : ".", &st) != -1)
  1494.     if (st.st_ino == old_ino && st.st_dev == old_dev)
  1495.         return;
  1496.     else {
  1497.         old_pos = pathpos;
  1498.         old_ino = st.st_ino;
  1499.         old_dev = st.st_dev;
  1500.     }
  1501.     if ((closure = q->closure))    /* (foo/)# - match zero or more dirs */
  1502.     if (q->closure == 2)    /* (foo/)## - match one or more dirs */
  1503.         q->closure = 1;
  1504.     else
  1505.         scanner(q->next);
  1506.     if ((c = q->comp)) {
  1507.     /* Now the actual matching for the current path section. */
  1508.     if (!(c->next || c->left) && !haswilds(c->str)) {
  1509.         /* It's a straight string to the end of the path section. */
  1510.         if (q->next) {
  1511.         /* Not the last path section. Just add it to the path. */
  1512.         int oppos = pathpos;
  1513.  
  1514.         if (errflag)
  1515.             return;
  1516.         if (q->closure && !strcmp(c->str, "."))
  1517.             return;
  1518.         if (!addpath(c->str))
  1519.             return;
  1520.         if (!closure || exists(pathbuf))
  1521.             scanner((q->closure) ? q : q->next);
  1522.         pathbuf[pathpos = oppos] = '\0';
  1523.         } else {
  1524.         /* Last path section.  See if there's a file there. */
  1525.         char *s;
  1526.  
  1527.         if (exists(s = getfullpath(c->str)))
  1528.             insert(dupstring(s));
  1529.         }
  1530.     } else {
  1531.         /* Do pattern matching on current path section. */
  1532.         char *fn;
  1533.         int dirs = !!q->next;
  1534.         struct dirent *de;
  1535.         DIR *lock = opendir((*pathbuf) ? unmeta(pathbuf) : ".");
  1536.  
  1537.         if (lock == NULL)
  1538.         return;
  1539.         while ((de = zreaddir(lock))) {
  1540.         /* Loop through the directory */
  1541.         if (errflag)
  1542.             break;
  1543.         /* fn is current file name in directory */
  1544.         fn = &de->d_name[0];
  1545.         /* skip this and parent directory */
  1546.         if (fn[0] == '.'
  1547.             && (fn[1] == '\0'
  1548.             || (fn[1] == '.' && fn[2] == '\0')))
  1549.             continue;
  1550.         /* prefix and suffix are zle trickery */
  1551.         if (!dirs && !colonmod &&
  1552.             ((glob_pre && !strpfx(glob_pre, fn))
  1553.              || (glob_suf && !strsfx(glob_suf, fn))))
  1554.             continue;
  1555.         if (domatch(fn, c, gf_noglobdots)) {
  1556.             /* if this name matchs the pattern... */
  1557.             int oppos = pathpos;
  1558.  
  1559.             if (dirs) {
  1560.             /* if not the last component in the path */
  1561.             if (closure) {
  1562.                 /* if matching multiple directories */
  1563.                 struct stat buf;
  1564.  
  1565.                 if ((q->follow ?
  1566.                 stat(unmeta(getfullpath(fn)), &buf) :
  1567.                 lstat(unmeta(getfullpath(fn)), &buf)) == -1) {
  1568.                 if (errno != ENOENT && errno != EINTR &&
  1569.                     errno != ENOTDIR) {
  1570.                     zerr("%e: %s", fn, errno);
  1571.                     errflag = 0;
  1572.                 }
  1573.                 continue;
  1574.                 }
  1575.                 if (!S_ISDIR(buf.st_mode))
  1576.                 continue;
  1577.             }
  1578.             /* do next path component */
  1579.             if (addpath(fn))
  1580.                 scanner((q->closure) ? q : q->next);    /* scan next level */
  1581.             pathbuf[pathpos = oppos] = '\0';
  1582.             } else
  1583.             insert(dyncat(pathbuf, fn));
  1584.             /* if the last filename component, just add it */
  1585.         }
  1586.         }
  1587.         closedir(lock);
  1588.     }
  1589.     } else
  1590.     zerr("no idea how you got this error message.", NULL, 0);
  1591. }
  1592.  
  1593. static char *pptr;        /* current place in string being matched */
  1594. static Comp tail = 0;
  1595. static int first;        /* are leading dots special? */
  1596.  
  1597. /* The main entry point for matching a string str against  *
  1598.  * a compiled pattern c.  `fist' indicates whether leading *
  1599.  * dots are special.                                       */
  1600.  
  1601. /**/
  1602. int
  1603. domatch(char *str, Comp c, int fist)
  1604. {
  1605.     pptr = str;
  1606.     first = fist;
  1607.     if (*pptr == Nularg)
  1608.     pptr++;
  1609.     return doesmatch(c);
  1610. }
  1611.  
  1612. #define untok(C)  (itok(C) ? ztokens[(C) - Pound] : (C))
  1613.  
  1614. /* See if pattern has a matching exclusion (~...) part */
  1615.  
  1616. /**/
  1617. int
  1618. excluded(Comp c, char *eptr)
  1619. {
  1620.     char *saves = pptr;
  1621.     int savei = first, ret;
  1622.  
  1623.     first = 0;
  1624.     pptr = (PATHADDP(c) && pathpos) ? getfullpath(eptr) : eptr;
  1625.  
  1626.     ret = doesmatch(c->exclude);
  1627.  
  1628.     pptr = saves;
  1629.     first = savei;
  1630.  
  1631.     return ret;
  1632. }
  1633.  
  1634. /* see if current string in pptr matches c */
  1635.  
  1636. /**/
  1637. int
  1638. doesmatch(Comp c)
  1639. {
  1640.     char *pat = c->str;
  1641.     int done = 0;
  1642.  
  1643.   tailrec:
  1644.     if (ONEHASHP(c) || (done && TWOHASHP(c))) {
  1645.     /* Do multiple matches like (pat)# and (pat)## */
  1646.     char *saves = pptr;
  1647.  
  1648.     if (first && *pptr == '.')
  1649.         return 0;
  1650.     if (doesmatch(c->next))
  1651.         return 1;
  1652.     pptr = saves;
  1653.     first = 0;
  1654.     }
  1655.     done++;
  1656.     for (;;) {
  1657.     /* loop until success or failure of pattern */
  1658.     if (!pat || !*pat) {
  1659.         /* No current pattern (c->str). */
  1660.         char *saves;
  1661.         int savei;
  1662.  
  1663.         if (errflag)
  1664.         return 0;
  1665.         /* Remember state in case we need to go back and   *
  1666.          * check for exclusion of pattern or alternatives. */
  1667.         saves = pptr;
  1668.         savei = first;
  1669.         /* Loop over alternatives with exclusions: (foo~bar|...). *
  1670.          * Exclusions apply to the pattern in c->left.            */
  1671.         if (c->left || c->right)
  1672.         if (!doesmatch(c->left) ||
  1673.             (c->exclude && excluded(c, saves)))
  1674.             if (c->right) {
  1675.             pptr = saves;
  1676.             first = savei;
  1677.             if (!doesmatch(c->right))
  1678.                 return 0;
  1679.             } else
  1680.             return 0;
  1681.         if (*pptr && CLOSUREP(c)) {
  1682.         /* With a closure (#), need to keep trying */
  1683.         pat = c->str;
  1684.         goto tailrec;
  1685.         }
  1686.         if (!c->next)    /* no more patterns left */
  1687.         return (!LASTP(c) || !*pptr);
  1688.         c = c->next;
  1689.         done = 0;
  1690.         pat = c->str;
  1691.         goto tailrec;
  1692.     }
  1693.     /* Don't match leading dot if first is set */
  1694.     if (first && *pptr == '.' && *pat != '.')
  1695.         return 0;
  1696.     if (*pat == Star) {    /* final * is not expanded to ?#; returns success */
  1697.         while (*pptr)
  1698.         pptr++;
  1699.         return 1;
  1700.     }
  1701.     first = 0;        /* finished checking start of pattern */
  1702.     if (*pat == Quest && *pptr) {
  1703.         /* match exactly one character */
  1704.         if (*pptr == Meta)
  1705.         pptr++;
  1706.         pptr++;
  1707.         pat++;
  1708.         continue;
  1709.     }
  1710.     if (*pat == Hat)    /* following pattern is negated */
  1711.         return 1 - doesmatch(c->next);
  1712.     if (*pat == Inbrack) {
  1713.         /* Match groups of characters */
  1714. #define PAT(X) (pat[X] == Meta ? pat[(X)+1] ^ 32 : untok(pat[X]))
  1715. #define PPAT(X) (pat[(X)-1] == Meta ? pat[X] ^ 32 : untok(pat[X]))
  1716.         char ch;
  1717. #ifdef HAVE_STRCOLL
  1718.         char l_buf[2], r_buf[2], ch_buf[2];
  1719.  
  1720.         l_buf[1] = r_buf[1] = ch_buf[1] = '\0';
  1721. #endif
  1722.  
  1723.         if (!*pptr)
  1724.         break;
  1725.         ch = *pptr == Meta ? pptr[1] ^ 32 : *pptr;
  1726. #ifdef HAVE_STRCOLL
  1727.         ch_buf[0] = ch;
  1728. #endif
  1729.         if (pat[1] == Hat || pat[1] == '^' || pat[1] == '!') {
  1730.         /* group is negated */
  1731.         pat[1] = Hat;
  1732.         for (pat += 2; *pat != Outbrack && *pat;
  1733.              *pat == Meta ? pat += 2 : pat++)
  1734.             if (*pat == '-' && pat[-1] != Hat && pat[1] != Outbrack) {
  1735. #ifdef HAVE_STRCOLL
  1736.             l_buf[0] = PPAT(-1);
  1737.             r_buf[0] = PAT(1);
  1738.             if (strcoll(l_buf, ch_buf) <= 0 &&
  1739.                 strcoll(ch_buf, r_buf) <= 0)
  1740. #else
  1741.             if (PPAT(-1) <= ch && PAT(1) >= ch)
  1742. #endif
  1743.                 break;
  1744.             } else if (ch == PAT(0))
  1745.             break;
  1746. #ifdef DEBUG
  1747.         if (!*pat) {
  1748.             zerr("something is very wrong.", NULL, 0);
  1749.             return 0;
  1750.         }
  1751. #endif
  1752.         if (*pat != Outbrack)
  1753.             break;
  1754.         pat++;
  1755.         *pptr == Meta ? pptr += 2 : pptr++;
  1756.         continue;
  1757.         } else {
  1758.         /* pattern is not negated (affirmed? asserted?) */
  1759.         for (pat++; *pat != Outbrack && *pat;
  1760.              *pat == Meta ? pat += 2 : pat++)
  1761.             if (*pat == '-' && pat[-1] != Inbrack &&
  1762.                    pat[1] != Outbrack) {
  1763. #ifdef HAVE_STRCOLL
  1764.             l_buf[0] = PPAT(-1);
  1765.             r_buf[0] = PAT(1);
  1766.             if (strcoll(l_buf, ch_buf) <= 0 &&
  1767.                 strcoll(ch_buf, r_buf) <= 0)
  1768. #else
  1769.             if (PPAT(-1) <= ch && PAT(1) >= ch)
  1770. #endif
  1771.                 break;
  1772.             } else if (ch == PAT(0))
  1773.             break;
  1774. #ifdef DEBUG
  1775.         if (!pat || !*pat) {
  1776.             zerr("oh dear.  that CAN'T be right.", NULL, 0);
  1777.             return 0;
  1778.         }
  1779. #endif
  1780.         if (*pat == Outbrack)
  1781.             break;
  1782.         for (*pptr == Meta ? pptr += 2 : pptr++;
  1783.              *pat != Outbrack; pat++);
  1784.         pat++;
  1785.         continue;
  1786.         }
  1787.     }
  1788.     if (*pat == Inang) {
  1789.         /* Numeric globbing. */
  1790.         unsigned long t1, t2, t3;
  1791.         char *ptr;
  1792.  
  1793.         if (*++pat == Outang || 
  1794.         (*pat == '-' && pat[1] == Outang && ++pat)) {
  1795.         /* <> or <->:  any number matches */
  1796.         (void)zstrtol(pptr, &ptr, 10);
  1797.         if (ptr == pptr)
  1798.             break;
  1799.         pptr = ptr;
  1800.         pat++;
  1801.         } else {
  1802.         /* Flag that there is no upper limit */
  1803.         int not3 = 0;
  1804.         /*
  1805.          * Form is <a-b>, where a or b are numbers or blank.
  1806.          * t1 = number supplied:  must be positive, so use
  1807.          * unsigned arithmetic.
  1808.          */
  1809.         t1 = (unsigned long)zstrtol(pptr, &ptr, 10);
  1810.         if (ptr == pptr)
  1811.             break;
  1812.         pptr = ptr;
  1813.         /* t2 = lower limit */
  1814.         t2 = (unsigned long)zstrtol(pat, &ptr, 10);
  1815.         if (*ptr != '-' || (not3 = (ptr[1] == Outang)))
  1816.                 /* exact match or no upper limit */
  1817.             t3 = t2, pat = ptr + not3;
  1818.         else        /* t3 = upper limit */
  1819.             t3 = (unsigned long)zstrtol(ptr + 1, &pat, 10);
  1820.         if (*pat++ != Outang)
  1821.             exit(21);
  1822.         if (t1 < t2 || (!not3 && t1 > t3))
  1823.             break;
  1824.         }
  1825.         continue;
  1826.     }
  1827.     if (*pptr == *pat) {
  1828.         /* just plain old characters */
  1829.         pptr++;
  1830.         pat++;
  1831.         continue;
  1832.     }
  1833.     break;
  1834.     }
  1835.     return 0;
  1836. }
  1837.  
  1838. /* turn a string into a Complist struct:  this has path components */
  1839.  
  1840. /**/
  1841. Complist
  1842. parsepat(char *str)
  1843. {
  1844.     mode = 0;            /* path components present */
  1845.     pptr = str;
  1846.     return parsecomplist();
  1847. }
  1848.  
  1849. /* turn a string into a Comp struct:  this doesn't treat / specially */
  1850.  
  1851. /**/
  1852. Comp
  1853. parsereg(char *str)
  1854. {
  1855.     remnulargs(str);
  1856.     mode = 1;            /* no path components */
  1857.     pptr = str;
  1858.     return parsecompsw(0);
  1859. }
  1860.  
  1861. /* Parse a series of path components pointed to by pptr */
  1862.  
  1863. /* This function tokenizes a zsh glob pattern */
  1864.  
  1865. /**/
  1866. Complist
  1867. parsecomplist(void)
  1868. {
  1869.     Comp c1;
  1870.     Complist p1;
  1871.     char *str;
  1872.  
  1873.     if (pptr[0] == Star && pptr[1] == Star &&
  1874.         (pptr[2] == '/' || (pptr[2] == Star && pptr[3] == '/'))) {
  1875.     /* Match any number of directories. */
  1876.     int follow;
  1877.  
  1878.     /* with three stars, follow symbolic links */
  1879.     follow = (pptr[2] == Star);
  1880.     pptr += (3 + follow);
  1881.  
  1882.     /* Now get the next path component if there is one. */
  1883.     p1 = (Complist) alloc(sizeof *p1);
  1884.     if ((p1->next = parsecomplist()) == NULL) {
  1885.         errflag = 1;
  1886.         return NULL;
  1887.     }
  1888.     p1->comp = (Comp) alloc(sizeof *p1->comp);
  1889.     p1->comp->stat |= C_LAST;    /* end of path component  */
  1890.     p1->comp->str = dupstring("*");
  1891.     *p1->comp->str = Star;        /* match anything...      */
  1892.     p1->closure = 1;        /* ...zero or more times. */
  1893.     p1->follow = follow;
  1894.     return p1;
  1895.     }
  1896.  
  1897.     /* Parse repeated directories such as (dir/)# and (dir/)## */
  1898.     if (*(str = pptr) == Inpar && !skipparens(Inpar, Outpar, &str) &&
  1899.         *str == Pound && str[-2] == '/') {
  1900.     pptr++;
  1901.     if (!(c1 = parsecompsw(0)))
  1902.         return NULL;
  1903.     if (pptr[0] == '/' && pptr[1] == Outpar && pptr[2] == Pound) {
  1904.         int pdflag = 0;
  1905.  
  1906.         pptr += 3;
  1907.         if (*pptr == Pound) {
  1908.         pdflag = 1;
  1909.         pptr++;
  1910.         }
  1911.         p1 = (Complist) alloc(sizeof *p1);
  1912.         p1->comp = c1;
  1913.         p1->closure = 1 + pdflag;
  1914.         p1->follow = 0;
  1915.         p1->next = parsecomplist();
  1916.         return (p1->comp) ? p1 : NULL;
  1917.     }
  1918.     } else {
  1919.     /* parse single path component */
  1920.     if (!(c1 = parsecompsw(1)))
  1921.         return NULL;
  1922.     /* then do the remaining path compoents */
  1923.     if (*pptr == '/' || !*pptr) {
  1924.         int ef = *pptr == '/';
  1925.  
  1926.         p1 = (Complist) alloc(sizeof *p1);
  1927.         p1->comp = c1;
  1928.         p1->closure = 0;
  1929.         p1->next = ef ? (pptr++, parsecomplist()) : NULL;
  1930.         return (ef && !p1->next) ? NULL : p1;
  1931.     }
  1932.     }
  1933.     errflag = 1;
  1934.     return NULL;
  1935. }
  1936.  
  1937. /* parse lowest level pattern */
  1938.  
  1939. /**/
  1940. Comp
  1941. parsecomp(void)
  1942. {
  1943.     Comp c = (Comp) alloc(sizeof *c), c1, c2;
  1944.     char cstr[PATH_MAX * 2], *s = cstr, *ls = NULL;
  1945.  
  1946.     /* In case of alternatives, code coming up is stored in tail. */
  1947.     c->next = tail;
  1948.  
  1949.     while (*pptr && (mode || *pptr != '/') && *pptr != Bar &&
  1950.        (!isset(EXTENDEDGLOB) || *pptr != Tilde ||
  1951.         !pptr[1] || pptr[1] == Outpar || pptr[1] == Bar) &&
  1952.        *pptr != Outpar) {
  1953.     /* Go through code until we find something separating alternatives,
  1954.      * or path components if relevant.
  1955.      */
  1956.     if (*pptr == Hat) {
  1957.         /* negate remaining pattern */
  1958.         *s++ = Hat;
  1959.         *s++ = '\0';
  1960.         pptr++;
  1961.         if (!(c->next = parsecomp()))
  1962.         return NULL;
  1963.         c->str = dupstring(cstr);
  1964.         return c;
  1965.     }
  1966.     if (*pptr == Star && pptr[1] &&
  1967.         (!isset(EXTENDEDGLOB) || pptr[1] != Tilde || !pptr[2] ||
  1968.          pptr[2] == Bar ||
  1969.          pptr[2] == Outpar) && (mode || pptr[1] != '/')) {
  1970.         /* Star followed by other patterns is treated like a closure
  1971.          * (zero or more repetitions) of the single character pattern
  1972.          * operator `?'.
  1973.          */
  1974.         *s++ = '\0';
  1975.         pptr++;
  1976.         c1 = (Comp) alloc(sizeof *c1);
  1977.         *(c1->str = dupstring("?")) = Quest;
  1978.         c1->stat |= C_ONEHASH;
  1979.         if (!(c2 = parsecomp()))
  1980.         return NULL;
  1981.         c1->next = c2;
  1982.         c->next = c1;
  1983.         c->str = dupstring(cstr);
  1984.         return c;
  1985.     }
  1986.     if (*pptr == Inpar) {
  1987.         /* Found a group (...) */
  1988.         char *startp = pptr, *endp;
  1989.         Comp stail = tail;
  1990.         int dpnd = 0;
  1991.  
  1992.         /* Need matching close parenthesis */
  1993.         if (skipparens(Inpar, Outpar, &pptr)) {
  1994.         errflag = 1;
  1995.         return NULL;
  1996.         }
  1997.         if (*pptr == Pound) {
  1998.         /* Zero (or one) or more repetitions of group */
  1999.         dpnd = 1;
  2000.         pptr++;
  2001.         if (*pptr == Pound) {
  2002.             pptr++;
  2003.             dpnd = 2;
  2004.         }
  2005.         }
  2006.         /* Parse the remaining pattern following the group... */
  2007.         if (!(c1 = parsecomp()))
  2008.         return NULL;
  2009.         /* ...remembering what comes after it... */
  2010.         tail = dpnd ? NULL : c1;
  2011.         /* ...before going back and parsing inside the group. */
  2012.         endp = pptr;
  2013.         pptr = startp;
  2014.         pptr++;
  2015.         *s++ = '\0';
  2016.         c->next = (Comp) alloc(sizeof *c);
  2017.         c->next->left = parsecompsw(0);
  2018.         /* Remember closures for group. */
  2019.         if (dpnd)
  2020.         c->next->stat |= (dpnd == 2) ? C_TWOHASH : C_ONEHASH;
  2021.         c->next->next = dpnd ? c1 : (Comp) alloc(sizeof *c);
  2022.         pptr = endp;
  2023.         tail = stail;
  2024.         c->str = dupstring(cstr);
  2025.         return c;
  2026.     }
  2027.     if (*pptr == Pound) {
  2028.         /* repeat whatever we've just had (ls) zero or more times */
  2029.         *s = '\0';
  2030.         pptr++;
  2031.         if (!ls)
  2032.         return NULL;
  2033.         if (*pptr == Pound) {
  2034.         /* need one or more matches: cheat by copying previous char */
  2035.         pptr++;
  2036.         c->next = c1 = (Comp) alloc(sizeof *c);
  2037.         c1->str = dupstring(ls);
  2038.         } else
  2039.         c1 = c;
  2040.         c1->next = c2 = (Comp) alloc(sizeof *c);
  2041.         c2->str = dupstring(ls);
  2042.         c2->stat |= C_ONEHASH;
  2043.         /* parse the rest of the pattern and return. */
  2044.         c2->next = parsecomp();
  2045.         if (!c2->next)
  2046.         return NULL;
  2047.         *ls++ = '\0';
  2048.         c->str = dupstring(cstr);
  2049.         return c;
  2050.     }
  2051.     ls = s;            /* whatever we just parsed */
  2052.     if (*pptr == Inang) {
  2053.         /* Numeric glob */
  2054.         int dshct;
  2055.  
  2056.         dshct = (pptr[1] == Outang);
  2057.         *s++ = *pptr++;
  2058.         while (*pptr && (*s++ = *pptr++) != Outang)
  2059.         if (s[-1] == '-')
  2060.             dshct++;
  2061.         else if (!idigit(s[-1]))
  2062.             break;
  2063.         if (s[-1] != Outang)
  2064.         return NULL;
  2065.     } else if (*pptr == Inbrack) {
  2066.         /* Character set: brackets had better match */
  2067.         while (*pptr && (*s++ = *pptr++) != Outbrack);
  2068.         if (s[-1] != Outbrack)
  2069.         return NULL;
  2070.     } else if (itok(*pptr) && *pptr != Star && *pptr != Quest) {
  2071.         /* something that can be tokenised which isn't otherwise special */
  2072.         *s++ = ztokens[*pptr++ - Pound];
  2073.     } else {
  2074.         /* any other character */
  2075.         *s++ = *pptr++;
  2076.     }
  2077.     }
  2078.     /* mark if last pattern component in path component or pattern */
  2079.     if (*pptr == '/' || !*pptr)
  2080.     c->stat |= C_LAST;
  2081.     *s++ = '\0';
  2082.     c->str = dupstring(cstr);
  2083.     return c;
  2084. }
  2085.  
  2086. /* Parse pattern possibly with different alternatives (|) */
  2087.  
  2088. /**/
  2089. Comp
  2090. parsecompsw(int pathadd)
  2091. {
  2092.     Comp c1, c2, c3, excl = NULL;
  2093.  
  2094.     c1 = parsecomp();
  2095.     if (!c1)
  2096.     return NULL;
  2097.     if (isset(EXTENDEDGLOB) && *pptr == Tilde) {
  2098.     /* Matching remainder of pattern excludes the pattern from matching */
  2099.     int oldmode = mode;
  2100.  
  2101.     mode = 1;
  2102.     pptr++;
  2103.     excl = parsecomp();
  2104.     mode = oldmode;
  2105.     if (!excl)
  2106.         return NULL;
  2107.     }
  2108.     if (*pptr == Bar || excl) {
  2109.     /* found an alternative or something to exclude */
  2110.     c2 = (Comp) alloc(sizeof *c2);
  2111.     if (*pptr == Bar) {
  2112.         /* get the next alternative after the | */
  2113.         pptr++;
  2114.         c3 = parsecompsw(pathadd);
  2115.         if (!c3)
  2116.         return NULL;
  2117.     } else {
  2118.         /* mark if end of pattern or path component */
  2119.         if (!*pptr || *pptr == '/')
  2120.         c2->stat |= C_LAST;
  2121.         c3 = NULL;
  2122.     }
  2123.     c2->str = dupstring("");
  2124.     c2->left = c1;
  2125.     c2->right = c3;
  2126.     c2->exclude = excl;
  2127.     if (pathadd)
  2128.         c2->stat |= C_PATHADD;
  2129.     return c2;
  2130.     }
  2131.     return c1;
  2132. }
  2133.  
  2134. /* blindly turn a string into a tokenised expression without lexing */
  2135.  
  2136. /**/
  2137. void
  2138. tokenize(char *s)
  2139. {
  2140.     char *t;
  2141.     int bslash = 0;
  2142.  
  2143.     for (; *s; s++) {
  2144.       cont:
  2145.     switch (*s) {
  2146.     case Bnull:
  2147.     case '\\':
  2148.         if (bslash) {
  2149.         s[-1] = Bnull;
  2150.         break;
  2151.         }
  2152.         bslash = 1;
  2153.         continue;
  2154.     case '[':
  2155.         if (bslash) {
  2156.         s[-1] = Bnull;
  2157.         break;
  2158.         }
  2159.         t = s;
  2160.         if (*++s == '^' || *s == '!')
  2161.         s++;
  2162.         while (*s && *++s != ']');
  2163.         if (!*s)
  2164.         return;
  2165.         *t = Inbrack;
  2166.         *s = Outbrack;
  2167.         break;
  2168.     case '<':
  2169.         if (isset(SHGLOB))
  2170.         break;
  2171.         if (bslash) {
  2172.         s[-1] = Bnull;
  2173.         break;
  2174.         }
  2175.         t = s;
  2176.         while (idigit(*++s));
  2177.         if (*s != '-')
  2178.         goto cont;
  2179.         while (idigit(*++s));
  2180.         if (*s != '>')
  2181.         goto cont;
  2182.         *t = Inang;
  2183.         *s = Outang;
  2184.         break;
  2185.     case '^':
  2186.     case '#':
  2187.     case '~':
  2188.         if (unset(EXTENDEDGLOB))
  2189.         break;
  2190.     case '(':
  2191.     case '|':
  2192.     case ')':
  2193.         if (isset(SHGLOB))
  2194.         break;
  2195.     case '*':
  2196.     case '?':
  2197.         for (t = ztokens; *t; t++)
  2198.         if (*t == *s) {
  2199.             if (bslash)
  2200.             s[-1] = Bnull;
  2201.             else
  2202.             *s = (t - ztokens) + Pound;
  2203.             break;
  2204.         }
  2205.     }
  2206.     bslash = 0;
  2207.     }
  2208. }
  2209.  
  2210. /* remove unnecessary Nulargs */
  2211.  
  2212. /**/
  2213. void
  2214. remnulargs(char *s)
  2215. {
  2216.     int nl = *s;
  2217.     char *t = s;
  2218.  
  2219.     while (*s)
  2220.     if (INULL(*s))
  2221.         chuck(s);
  2222.     else
  2223.         s++;
  2224.     if (!*t && nl) {
  2225.     t[0] = Nularg;
  2226.     t[1] = '\0';
  2227.     }
  2228. }
  2229.  
  2230. /* qualifier functions:  mostly self-explanatory, see glob(). */
  2231.  
  2232. /* device number */
  2233.  
  2234. /**/
  2235. int
  2236. qualdev(struct stat *buf, long dv)
  2237. {
  2238.     return buf->st_dev == dv;
  2239. }
  2240.  
  2241. /* number of hard links to file */
  2242.  
  2243. /**/
  2244. int
  2245. qualnlink(struct stat *buf, long ct)
  2246. {
  2247.     return (range < 0 ? buf->st_nlink < ct :
  2248.         range > 0 ? buf->st_nlink > ct :
  2249.         buf->st_nlink == ct);
  2250. }
  2251.  
  2252. /* user ID */
  2253.  
  2254. /**/
  2255. int
  2256. qualuid(struct stat *buf, long uid)
  2257. {
  2258.     return buf->st_uid == uid;
  2259. }
  2260.  
  2261. /* group ID */
  2262.  
  2263. /**/
  2264. int
  2265. qualgid(struct stat *buf, long gid)
  2266. {
  2267.     return buf->st_gid == gid;
  2268. }
  2269.  
  2270. /* device special file? */
  2271.  
  2272. /**/
  2273. int
  2274. qualisdev(struct stat *buf, long junk)
  2275. {
  2276.     junk = buf->st_mode & S_IFMT;
  2277.     return junk == S_IFBLK || junk == S_IFCHR;
  2278. }
  2279.  
  2280. /* block special file? */
  2281.  
  2282. /**/
  2283. int
  2284. qualisblk(struct stat *buf, long junk)
  2285. {
  2286.     junk = buf->st_mode & S_IFMT;
  2287.     return junk == S_IFBLK;
  2288. }
  2289.  
  2290. /* character special file? */
  2291.  
  2292. /**/
  2293. int
  2294. qualischar(struct stat *buf, long junk)
  2295. {
  2296.     junk = buf->st_mode & S_IFMT;
  2297.     return junk == S_IFCHR;
  2298. }
  2299.  
  2300. /* file type is requested one */
  2301.  
  2302. /**/
  2303. int
  2304. qualmode(struct stat *buf, long mod)
  2305. {
  2306.     return (buf->st_mode & S_IFMT) == mod;
  2307. }
  2308.  
  2309. /* given flag is set in mode */
  2310.  
  2311. /**/
  2312. int
  2313. qualflags(struct stat *buf, long mod)
  2314. {
  2315.     return buf->st_mode & mod;
  2316. }
  2317.  
  2318. /* mode matches number supplied exactly  */
  2319.  
  2320. /**/
  2321. int
  2322. qualeqflags(struct stat *buf, long mod)
  2323. {
  2324.     return (buf->st_mode & 07777) == mod;
  2325. }
  2326.  
  2327. /* regular executable file? */
  2328.  
  2329. /**/
  2330. int
  2331. qualiscom(struct stat *buf, long mod)
  2332. {
  2333.     return (buf->st_mode & (S_IFMT | S_IEXEC)) == (S_IFREG | S_IEXEC);
  2334. }
  2335.  
  2336. /* size in required range? */
  2337.  
  2338. /**/
  2339. int
  2340. qualsize(struct stat *buf, long size)
  2341. {
  2342.     unsigned long scaled = buf->st_size;
  2343.  
  2344.     switch (units) {
  2345.     case TT_POSIX_BLOCKS:
  2346.     scaled += 511l;
  2347.     scaled /= 512l;
  2348.     break;
  2349.     case TT_KILOBYTES:
  2350.     scaled += 1023l;
  2351.     scaled /= 1024l;
  2352.     break;
  2353.     case TT_MEGABYTES:
  2354.     scaled += 1048575l;
  2355.     scaled /= 1048576l;
  2356.     break;
  2357.     }
  2358.  
  2359.     return (range < 0 ? scaled < size :
  2360.         range > 0 ? scaled > size :
  2361.         scaled == size);
  2362. }
  2363.  
  2364. /* time in required range? */
  2365.  
  2366. /**/
  2367. int
  2368. qualtime(struct stat *buf, long days)
  2369. {
  2370.     time_t now, diff;
  2371.  
  2372.     time(&now);
  2373.     diff = now - (amc == 0 ? buf->st_atime : amc == 1 ? buf->st_mtime :
  2374.           buf->st_ctime);
  2375.     /* handle multipliers indicating units */
  2376.     switch (units) {
  2377.     case TT_DAYS:
  2378.     diff /= 86400l;
  2379.     break;
  2380.     case TT_HOURS:
  2381.     diff /= 3600l;
  2382.     break;
  2383.     case TT_MINS:
  2384.     diff /= 60l;
  2385.     break;
  2386.     case TT_WEEKS:
  2387.     diff /= 604800l;
  2388.     break;
  2389.     case TT_MONTHS:
  2390.     diff /= 2592000l;
  2391.     break;
  2392.     }
  2393.  
  2394.     return (range < 0 ? diff < days :
  2395.         range > 0 ? diff > days :
  2396.         diff == days);
  2397. }
  2398.  
  2399.